using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0628. 三个数的最大乘积")]
    public class No0628_MaximumProduct : AbsBaseTestItem
    {
        /*
        给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
        示例 1:
            输入: [1,2,3]
            输出: 6
        示例 2:
            输入: [1,2,3,4]
            输出: 24
        注意:
            给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
            输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
        */

        public override void OnTest()
        {
            OnExecuteFunction(MaximumProduct_Sort);
            OnExecuteFunction(MaximumProduct_LinearScan);
        }
        private void OnExecuteFunction(Func<int[], int> func)
        {
            Assert.TestExe(func, new int[] { 1, 2, 3 }, 6);
            Assert.TestExe(func, new int[] { 1, 2, 3, 4 }, 24);
        }

        /// <summary>
        /// 方法一：排序
        /// </summary>
        public int MaximumProduct_Sort(int[] nums)
        {
            Array.Sort(nums);
            int n = nums.Length;
            int value1 = nums[0] * nums[1] * nums[n - 1];
            int value2 = nums[n - 3] * nums[n - 2] * nums[n - 1];
            return Math.Max(value1, value2);
        }

        /// <summary>
        /// 方法二：线性扫描
        /// </summary>
        public int MaximumProduct_LinearScan(int[] nums)
        {
            int min1 = int.MaxValue, min2 = int.MaxValue;
            int max1 = int.MinValue, max2 = int.MinValue, max3 = int.MinValue;
            foreach (int x in nums)
            {
                if (x < min1)
                {
                    min2 = min1;
                    min1 = x;
                }
                else if (x < min2)
                {
                    min2 = x;
                }

                if (x > max1)
                {
                    max3 = max2;
                    max2 = max1;
                    max1 = x;
                }
                else if (x > max2)
                {
                    max3 = max2;
                    max2 = x;
                }
                else if (x > max3)
                {
                    max3 = x;
                }
            }
            return Math.Max(min1 * min2 * max1, max3 * max2 * max1);
        }
    }
}
